package com.sise.Backtracking;


/**
 *      37. 解数独
 *      
 *      编写一个程序，通过填充空格来解决数独问题。
 *
 *      数独的解法需 遵循如下规则：
 *
 *      数字 1-9 在每一行只能出现一次。
 *      数字 1-9 在每一列只能出现一次。
 *      数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 *      数独部分空格内已填入了数字，空白格用 '.' 表示。
 *
 *
 *      5 3 . . 7 . . . .
 *      6 . . 1 9 5 . . .
 *      . 9 8 . . . . 6 .
 *      8 . . . 6 . . . 3
 *      4 . . 8 . 3 . . 1
 *      7 . . . 2 . . . 6
 *      . 6 . . . . 2 8 .
 *      . . . 4 1 9 . . 5
 *      . . . . 8 . . 7 9
 *
 *  结果：
 *      5 3 4 6 7 8 9 1 2
 *      6 7 2 1 9 5 3 4 8
 *      1 9 8 3 4 2 5 6 7
 *      8 5 9 7 6 1 4 2 3
 *      4 2 6 8 5 3 7 9 1
 *      7 1 3 9 2 4 8 5 6
 *      9 6 1 5 3 7 2 8 4
 *      2 8 7 4 1 9 6 3 5
 *      3 4 5 2 8 6 1 7 9
 *
 *      疑惑：一开始对于数字的重复使用，个人考虑使用的是 Set，后续才发现每一行、每一列都需要去重，故此需要使用 二维数组，例如 row[1][2] 表示 第一行的 2 数字 已经被使用
 *
 *      解题思路： 根据题意初始化数据，使用二位数组 Boolean 进行组装，使用递归回溯，++j 已经 j >= 9 换行进行每一行的遍历使用，
 *               同时检查 行、列、宫格 中的数据是否被使用。
 */
public class _37_solveSudoku {

    public void solveSudoku(char[][] board) {

        /**
         * 记录某行，某位数字是否已经被摆放
         */
        boolean[][] row = new boolean[9][9];

        /**
         * 记录某列，某位数组是否已经被摆放
         */
        boolean[][] col = new boolean[9][9];

        /**
         * 记录 3x3 宫格中，某位数字是否已经被摆放
         */
        boolean[][] block = new boolean[9][9];


        // 因为题干中已经给出原始数据，所以这里进行数据初始化，确保那些数据已经被使用
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';    // 因为这里使用的是 char，故此减去 '1' 才可以得到 int 类型的数值
                    row[i][num] = true;             // 假设 board[1][5] = 7，那么 row[1][7 -> num] = true，说明第二行的 7 已经被使用过了
                    col[j][num] = true;
                    block[i / 3 * 3 + j / 3][num] = true;   // blockIndex = i / 3 * 3 + j / 3，取整
                }
            }
        }

        dfs(board, row, col, block, 0, 0);
    }

    private boolean dfs(char[][] board, boolean[][] row, boolean[][] col, boolean[][] block, int i, int j) {
        // 寻找空位置
        while (board[i][j] != '.') {
            // 先进行 ++j，保证遍历的是下一列数据。目的：遍历每一行中的每一列，当列数超过 9，那么就进行换行
            if (++j >= 9) {
                i++;
                j = 0;
            }

            // 如果超过九行，那么就说明此次遍历完成 => 递归退出条件
            if (i >= 9) {
                return true;
            }
        }

        // 这里遍历的不是 i、j，而是 num。也就是说，每次递归中的 每个位置都有成为 0~9 的权利
        for (int num = 0; num < 9; num++) {
            int blockIndex = i / 3 * 3 + j / 3;             // 获取当前属于第几个方格
            if (!row[i][num] && !col[j][num] && !block[blockIndex][num]) {      // 检查 列、行、宫格 是否有重复数据
                // 递归
                board[i][j] = (char) ('1' + num);
                row[i][num] = true;
                col[j][num] = true;
                block[blockIndex][num] = true;

                // 这里的 dfs 不需要对 i、j 进行 +1，因为在递归的最开始就已经有判断 board[i][j] != '.' ，故此对于相同的 i、j，循环后自动跳过
                if (dfs(board, row, col, block, i, j)) {
                    return true;
                } else {
                    // 回溯
                    row[i][num] = false;
                    col[j][num] = false;
                    block[blockIndex][num] = false;
                    board[i][j] = '.';
                }
            }
        }
        return false;
    }

    private void printBoard(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        _37_solveSudoku solution = new _37_solveSudoku();
        solution.printBoard(board);
        solution.solveSudoku(board);
        solution.printBoard(board);
    }
}

